#include "common.h"

int ans;
void findKthLargest1(vector<int>& nums, int k, int start, int end)
{
	if (start == end && end == k - 1)
	{
		ans = nums[end];
		return;
	}
	if (start >= end) return;
	int basic = nums[start];
	int i = start;
	int j = end;
	while (i < j)
	{
		while (nums[j] < basic && i < j) j--;
		nums[i] = nums[j];
		while (nums[i] >= basic && i < j) i++;
		nums[j] = nums[i];
	}
	nums[i] = basic;
	if (i + 1 < k) findKthLargest1(nums, k, i + 1, end);
	else if (i + 1 > k) findKthLargest1(nums, k, start, i - 1);
	else
	{
		ans = nums[i];
	}
}
int findKthLargest(vector<int>& nums, int k)
{
	vector<int> temp = nums;
	findKthLargest1(temp, k, 0, nums.size() - 1);
	return ans;
}